import sys,math
import threading
input=sys.stdin.readline
sys.setrecursionlimit(10**8)
def main():
def dfs(gp,v,c,i):
if v[i]==1:
return 0
v[i]=1
ans=0
for x in range(len(gp[i])):
if gp[i][x][1]<c:
ans=max(ans,dfs(gp,v,gp[i][x][1],gp[i][x][0])+1)
else:
ans=max(ans,dfs(gp,v,gp[i][x][1],gp[i][x][0]))
return ans
for _ in range(int(input())):
n=int(input())
d={1:0}
ans=1
gp=[]
for i in range(n):
gp.append([])
for i in range(n-1):
u,v=map(int,input().split())
gp[u-1].append([v-1,i])
gp[v-1].append([u-1,i])
v=[0]*n
print(dfs(gp,v,-1,0)+1)
threading.stack_size(10 ** 8)
t = threading.Thread(target=main)
t.start()
t.join()#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define dbg(...) 42
#endif
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int tt;cin >> tt;
while(tt--){
int n;
cin >> n;
vector<pair<int,int>>adj[n];
for(int i = 0; i < n - 1; i++){
int x,y;
cin >> x >> y;
--x,--y;
adj[x].push_back({y,i});
adj[y].push_back({x,i});
}
int a = 1;
function<void(int,int,int, int )>dfs = [&](int u, int p, int h, int from){
a = max(a, h);
for (auto [x,y] : adj[u]){
if (x == p)continue;
dfs(x,u,h + (y < from), y);
}
};
dfs(0,0,1,0);
cout<<a<<'\n';
}
return 0;
}
544B - Sea and Islands | 152B - Steps |
1174D - Ehab and the Expected XOR Problem | 1511A - Review Site |
1316A - Grade Allocation | 838A - Binary Blocks |
1515D - Phoenix and Socks | 1624D - Palindromes Coloring |
1552F - Telepanting | 1692G - 2Sort |
1191A - Tokitsukaze and Enhancement | 903A - Hungry Student Problem |
52B - Right Triangles | 1712A - Wonderful Permutation |
1712D - Empty Graph | 1712B - Woeful Permutation |
1712C - Sort Zero | 1028B - Unnatural Conditions |
735B - Urbanization | 746C - Tram |
1278B - A and B | 1353D - Constructing the Array |
1269C - Long Beautiful Integer | 1076A - Minimizing the String |
913C - Party Lemonade | 1313A - Fast Food Restaurant |
681A - A Good Contest | 1585F - Non-equal Neighbours |
747A - Display Size | 285A - Slightly Decreasing Permutations |